//给你一个单链表，随机选择链表的一个节点，并返回相应的节点值。每个节点 被选中的概率一样 。 
//
// 实现 Solution 类： 
//
// 
// Solution(ListNode head) 使用整数数组初始化对象。 
// int getRandom() 从链表中随机选择一个节点并返回该节点的值。链表中所有节点被选中的概率相等。 
// 
//
// 
//
// 示例： 
//
// 
//输入
//["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"]
//[[[1, 2, 3]], [], [], [], [], []]
//输出
//[null, 1, 3, 2, 2, 3]
//
//解释
//Solution solution = new Solution([1, 2, 3]);
//solution.getRandom(); // 返回 1
//solution.getRandom(); // 返回 3
//solution.getRandom(); // 返回 2
//solution.getRandom(); // 返回 2
//solution.getRandom(); // 返回 3
//// getRandom() 方法应随机返回 1、2、3中的一个，每个元素被返回的概率相等。 
//
// 
//
// 提示： 
//
// 
// 链表中的节点数在范围 [1, 10⁴] 内 
// -10⁴ <= Node.val <= 10⁴ 
// 至多调用 getRandom 方法 10⁴ 次 
// 
//
// 
//
// 进阶： 
//
// 
// 如果链表非常大且长度未知，该怎么处理？ 
// 你能否在不使用额外空间的情况下解决此问题？ 
// 
// Related Topics 水塘抽样 链表 数学 随机化 👍 188 👎 0

package com.cute.leetcode.editor.cn;

import java.util.Random;

public class LinkedListRandomNode {
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        ListNode node1 = new ListNode(2);
        ListNode node2 = new ListNode(3);
        head.next = node1;node1.next = node2;
    }
    //leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */


class Solution {
    /**
     * 思路如下：传入的是链表的头节点，先遍历一边链表得到长度
     * getRandom中使用随机数，然后遍历取到该位置的节点即可
     */
    int size;
    ListNode head;
    Random random;
    public Solution(ListNode head) {
        this.head = head;
        this.size = 0;
        this.random = new Random();
        ListNode node = head;
        while (node != null){
            size++;
            node = node.next;
        }
    }
    public int getRandom() {
        //取得随机数，记得+1，因为是左闭右开的，而且默认从0开始的
        int random = (int) (Math.random() * size) + 1;
        ListNode temp = head;
        while (--random != 0) temp = temp.next;
        return temp.val;
    }

    /**
     * 蓄水池算法：大数据随机抽样，满的蓄水池中加入一滴水就必然有一滴离开
     * 适用于长度很大且长度会动态变化的过程，且不需要额外的空间
     */
    public int getRandom2() {
        int res = 0;
        ListNode cur = head;
        int count = 0;
        while (cur != null){
            count++;//记录下标
            int r = random.nextInt(count)+1;
            // 保证每一个数据都能等概率的被取到，因为是从前到后取的数据
            if (r == count) res = cur.val;
            cur = cur.next;
        }
        return res;
    }

}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(head);
 * int param_1 = obj.getRandom();
 */
//leetcode submit region end(Prohibit modification and deletion)

    public static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
}
